#include "binTree.h"
#include <stack>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

BinTree::BinTree()
{
    //creat a tree here manually
    Node** nodeList = new Node*[10];

    for(int i = 0; i < 10; i++ )
        nodeList[i] = new Node(i+1);
    nodeList[0]->setLChild(nodeList[1]);
    nodeList[0]->setRChild(nodeList[2]);

    nodeList[1]->setRChild(nodeList[3]);

    nodeList[3]->setLChild(nodeList[4]);
    nodeList[3]->setRChild(nodeList[5]);

    nodeList[4]->setLChild(nodeList[6]);
    nodeList[4]->setRChild(nodeList[7]);

    nodeList[7]->setRChild(nodeList[8]);

    nodeList[8]->setRChild(nodeList[9]);
    root = nodeList[0];
}

vector<Node *> BinTree::preOrderTraverse()
{
    //pre-order without recursion
    vector<Node *> result;
    stack<Node *> nodeStack;
    Node *p = root;
    while(p || !nodeStack.empty())
    {
        if(p)
        {
            result.push_back(p);        //push p into result stack
            nodeStack.push(p);
            p = p->getLChild();
        }
        else
        {
            p = nodeStack.top();
            nodeStack.pop();
            p = p->getRChild();
        }
    }
    return result;
}

vector<Node *> BinTree::inOrderTraverse()
{
    vector<Node *> result;
    stack<Node *> nodeStack;
    Node *p = root;
    while (p || !nodeStack.empty())
    {
        if (p)
        {
            nodeStack.push(p);
            p = p -> getLChild();
        }
        else
        {
            p = nodeStack.top();
            nodeStack.pop();
            result.push_back(p);
            p = p -> getRChild();
        }
    }
    return result;

}

struct StackElementType
{
    Node* ptr;
    int flag;
};

vector<Node *> BinTree::postOrderTraverse()
{
    Node *p = root;
    StackElementType element;
    vector<Node *> result;
    stack<StackElementType> nodeStack;
    while (p || !nodeStack.empty())
    {
        if (p)
        {
            element.ptr = p;
            element.flag = 1;
            nodeStack.push(element);
            p = p->getLChild();
        }
        else
        {
            element = nodeStack.top();
            nodeStack.pop();
            if (element.flag)
            {
                element.flag = 0;
                p = element.ptr -> getRChild();
                nodeStack.push(element);
            }
            else
            {
                p = element.ptr;
                result.push_back(p);
                p = NULL;
            }
        }
    }
    return result;
}

vector<Node *> BinTree::levelTraverse()
{
    Node *p = root;
    queue<Node *> nodeQueue;
    vector<Node *> result;
    nodeQueue.push(p);
    while (p || !nodeQueue.empty())
    {
        p = nodeQueue.front();
        nodeQueue.pop();
        if(p)
        {
            result.push_back(p);
            nodeQueue.push(p->getLChild());
            nodeQueue.push(p->getRChild());
        }
    }
    return result;
}

